
"""
100. 相同的树
"""
from typing import Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    def __init__(self):
        self.is_same = True

    def isSameTree1(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        """
        方法1，遍历二叉树
        维护一个外部变量，记录当前两个节点是否相同
        """
        self.traverse(p, q)
        return self.is_same

    '''遍历二叉树'''
    def traverse(self, p: Optional[TreeNode], q: Optional[TreeNode]):
        # 判断外部变量，不满足直接退出
        if not self.is_same:
            self.is_same = False
            return

        # 都为空，直接退出
        if not p and not q:
            return

        # 存在一个为空，不满足，退出
        if not p or not q:
            self.is_same = False
            return

        if p.val != q.val:
            self.is_same = False
            return

        self.traverse(p.left, q.left)
        self.traverse(p.right, q.right)

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        """
        方法2，分解二叉树
         * 思考：可以将原问题拆分成子问题，即先判断根节点是否相同，再判断左右子树是否都相同
         * 定义：输入两个二叉树节点，返回他们两是否相同
        """
        # 都为空，直接退出
        if not p and not q:
            return True

        # 存在一个为空，不满足，退出
        if not p or not q:
            return False

        if p.val != q.val:
            return False

        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)